// 思路：在无序序列找一个基准，和基准比较，将大于基准的移动到基准右侧，将小于基准的移动到基准左侧，然后递归的处理子序列

function quickSort(arr, start = 0, end = 7) {
    if (start < end) {
        let index = partition(arr, start, end)
        quickSort(arr, start, index - 1)
        quickSort(arr, index + 1, end)
    }
    return arr
}

function partition(arr, start, end) {
    let randomIndex = Math.floor(Math.random() * (end - start)) + start
    let pivot = arr[randomIndex];
    // 把基准值和首位值交换，然后从第二个元素开始比较
    [arr[randomIndex], arr[start]] = [arr[start], arr[randomIndex]];
    let i = start + 1
    // 双指针思路，i为慢指针，j为快指针，保证i之前的元素都小于基准数
    // 以最低位为基准数，然后将序列中比基准数大的元素移动到基准数右侧
    // 比基准数小的移动到基准数左侧，最后将基准数放到正确的位置上
    // 从基准数1位开始开始遍历，保证位置i之前的元素都小于基准数
    for (let j = i; j <= end; j++) {
        if (arr[j] < pivot) {
            // 将小于基准的元素arr[j] 与当前arr[i]进行交换，保证位置i之前的元素小于基准数
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++
        }
    }
    [arr[start], arr[i - 1]] = [arr[i - 1], arr[start]];
    return i - 1
}

// 时间复杂度为Onlogn
// 空间复杂度，最坏On，最好Ologn

let arr2 = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(quickSort(arr2))